//给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。 
//
// 请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你
//设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。 
//
// 返回分配方案中尽可能 最小 的 最大工作时间 。 
//
// 
//
// 示例 1： 
//
// 
//输入：jobs = [3,2,3], k = 3
//输出：3
//解释：给每位工人分配一项工作，最大工作时间是 3 。
// 
//
// 示例 2： 
//
// 
//输入：jobs = [1,2,4,7,8], k = 2
//输出：11
//解释：按下述方式分配工作：
//1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
//2 号工人：4、7（工作时间 = 4 + 7 = 11）
//最大工作时间是 11 。 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= jobs.length <= 12 
// 1 <= jobs[i] <= 10⁷ 
// 
// Related Topics位运算 | 数组 | 动态规划 | 回溯 | 状态压缩 
//
// 👍 294, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class FindMinimumTimeToFinishAllJobs {
    public static void main(String[] args) {
        Solution solution = new FindMinimumTimeToFinishAllJobs().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[] bucket;
        int ans = Integer.MAX_VALUE;

        public int minimumTimeRequired(int[] jobs, int k) {
            Arrays.sort(jobs);
            this.bucket = new int[k];
            backTracking(jobs, jobs.length - 1, k);
            return ans;
        }

        public void backTracking(int[] jobs, int i, int k) {
            // 统计最小值
            if (i < 0) {
                int max = 0;
                for (int b : bucket) {
                    max = Math.max(b, max);
                }
                ans = Math.min(ans, max);
                return;
            }

            // 剩下的分配不完
            int count = 0;
            for (int b : bucket) {
                if (b == 0) count++;
            }
            if (count > i + 1) return;

            // 如果某个员工大于了之前搜索过的，搜索下去也不是最优的
            for (int b : bucket) {
                if (b > ans) return;
            }

            for (int j = 0; j < k; j++) {
                // 第一个给哪个员工都是一样的
                if (i == jobs.length - 1 && j > 0) continue;
                if (j > 0 && bucket[j] == bucket[j - 1]) continue;

                bucket[j] += jobs[i];
                backTracking(jobs, i - 1, k);
                bucket[j] -= jobs[i];
            }

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
